An image may contain a variety of objects, such as a bicycle, a car, a soda can, an apple, etc. Multiclass classification methods can find which objects are present in a given object. A common framework for such classification islabel=arg maxk wk*x, where k is the name of the object (e.g., “wheel”), Wk is a learned vector useful in determining if the object is in an image (for example, wwheel is a “wheel” vector) and x is a vector representing the image against which wk is evaluated. An object may belong to a class of objects. For example, a class of objects may be car and an object may be a particular make (e.g., manufacturer), style (e.g., two/four door sedan, sports car, truck, etc.), and/or particular vehicle. As used herein, a class may be used generally to describe an object. For example, reference to a classifier vector may include an object vector. In an implementation, a class may consist of one object and a classifier vector can be an object vector. The term “label” may be the score that results when a particular object vector is evaluated against a given image. For example, a higher label score in the above example may indicate a higher likelihood that the tested image contains a wheel. The label may indicate, for example, that an object such as a bicycle is present in an image, or that an object belonging to the class “automobile” is present in the image.
The term wk*X refers to the dot product between wk and x. One way to determine which objects (or classes of objects) are in an image is to analyze the image against all of the known object vectors. But such a linear scan of all object vectors (or classifier vectors) may be inefficient when the number of possible objects (and therefore object vectors) is large. Tree-based and hash-based methods have been utilized to improve search efficiency, for example, in sublinear time nearest-neighbor searches. Although such techniques can be useful, they depend on a distance being defined between vectors as opposed to the dot product shown above.